package com.example.demo.dichotomy;

public class MyBinarySearch {


    /**
     * 二分查找法，搜索某个值
     *
     * @param nums
     * @param k
     */
    public void findNum(int[] nums, int k) {
        // 应该先对数组排序
        quick(nums, 0, nums.length - 1);
//        for (int i:nums) {
//            System.out.print(i+" ");
//        }
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int middle = (low + high) / 2;
            System.out.println("1=" + middle);
            if (nums[middle] > k) {
                high = middle - 1;
            } else if (nums[middle] < k) {
                low = middle + 1;
            } else {
                System.out.println("middle=" + middle);
                break;
            }
        }
    }

    // 快速排序
    private void quick(int[] nums, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low, j = high;
        int temp = nums[low];
        while (i < j) {
            while (i < j && nums[j] >= temp) {
                j--;
            }
            while (i < j && nums[i] <= temp) {
                i++;
            }
            if (i < j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
        nums[low] = nums[i];
        nums[i] = temp;
        quick(nums, low, j - 1);
        quick(nums, j + 1, high);
    }
}

class TestBinarySearch {

    public static void main(String[] args) {
        MyBinarySearch mbs = new MyBinarySearch();
        int[] nums = {4, 5, 1, 2, 8, 3, 9, 6, 7};
        mbs.findNum(nums, 6);
    }
}